package com.sakura.二分查找;

import java.util.Arrays;

public class Code03_和有限的最长子序列 {

    public static void main(String[] args) {
//        int[] nums = {4, 5, 2, 1};
//        int[] queries = {3, 10, 21};
//        System.out.println(Arrays.toString(new Code03_和有限的最长子序列().answerQueries(nums, queries)));
    }

    public int[] answerQueries_1(int[] nums, int[] queries) {
        // 1 排序
        Arrays.sort(nums);
        // 2 前缀和
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        // 3 二分查找
        for (int i = 0; i < queries.length; i++) {
            queries[i] = lowerBound(nums, queries[i]);
        }
        return queries;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
           if (nums[mid] > target) {
               right = mid;
           } else {
               left = mid;
           }
        }
        return right;
    }

    /**
     * 思考题：将子序列换成子数组
     *  滑动窗口
     */
    public int[] answerQueries_2(int[] nums, int[] queries) {
        int n = queries.length;
        for (int i = 0; i < queries.length; i++) {
            int maxLen = 0;
            for (int l = 0, r = 0, sum = 0; r < n; r++) {
                sum += nums[r];
                while (sum > queries[i]) {
                    sum -= nums[l++];
                }
                if (sum <= queries[i]) {
                    maxLen = Math.max(maxLen, r - l + 1);
                }
            }
            queries[i] = maxLen;

        }
        return queries;
    }
}
